/**
 * https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
 * 二叉树后序遍历
 * @param root 
 */
const postorderTraversal = (root: TreeNode | null): number[] => {
    // 树为空
    if (root == null) return []

    const arr: number[] = []

    /**
     * 获取n的前驱节点
     * @param n 
     */
    const getAced = (n: TreeNode) => {
        let left = n.left;

        while (left !== null && left.right !== null && left.right !== n) {
            left = left.right;
        }

        return left;
    }

    /**
     * 逆序
     * @param from 
     */
    const reverse = (from: TreeNode | null): TreeNode | null => {
        let prev = null,
            next = null;

        while (from !== null) {
            // 保存下一个
            next = from.right;

            // from的下一个指向上一个
            from.right = prev;

            // prev赋值为from
            prev = from

            from = next!;
        }

        return prev;
    }

    /**
     * 逆序访问节点
     * @param n 
     */
    const printNode = (n: TreeNode) => {
        let node = reverse(n),
            n2 = node;
        while (node !== null) {
            arr.push(node.val);
            node = node.right;
        }
        // 恢复
        reverse(n2);
    }
    let tmp = root;
    while (root !== null) {
        if (root.left !== null) {
            // 找到前驱节点, 指向自己
            const aced: TreeNode = getAced(root)!

            if (aced.right === null) {
                aced.right = root;
                root = root.left
            } else if (aced.right === root) {
                // 第二次访问该节点

                aced.right = null

                // 逆序访问节点
                console.log(root.left)
                printNode(root.left);
                root = root.right;
            }

        } else {
            // 访问右节点
            root = root.right;
        }
    }

    //! 最后的打印, 要记得
    printNode(tmp)


    return arr;
};

const postorderTraversal2 = (root: TreeNode | null): number[] => {
    // 树为空
    if (root == null) return []

    const arr: number[] = []

    const postOrder = (n: TreeNode | null) => {
        if (n === null) return;
        // 访问左节点
        postOrder(n.left);

        // 访问右节点
        postOrder(n.right);

        // 访问节点
        arr.push(n.val)
    }

    postOrder(root)

    return arr;
};